package leetcode;


public class FriendCircle {

	public static void main(String[] args) {
		int[][] M = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		FriendCircle object = new FriendCircle();
		System.out.println(object.findCircleNum(M));
	}
	
	private class UnionFind{
		int[] id;
		int count;
		
		public UnionFind(int m){
			id = new int[m];
			for(int i = 0; i < m; i++){
				id[i] = i;
			}
			count = m;
		}
		
		public void union(int p, int q){
			if(p == q){
				return;
			}
			int pId = find(p);
			int qId = find(q);
			if(pId == qId){
				return;
			}
			id[pId] = qId;
			count--;
		}
		
		public int find(int p){
			if(id[p] != p){
				id[p] = find(id[p]);
			}
			return id[p];
		}
	}
	
	//并查集
    public int findCircleNum(int[][] M) {
        if(M == null || M.length <= 0){
        	return 0;
        }
        int rows = M.length;
        UnionFind uf = new UnionFind(rows);
        for(int i = 0; i < rows; i++){
        	for(int j = 0; j < rows; j++){
        		if(M[i][j] == 1){
        			uf.union(i, j);
        		}
        	}
        }
        return uf.count;
    }
    
}
